package merge_sort;

public class sort {
    /*
     * 归并排序
     * 时间复杂度：最好：O（NlogN）
     * 空间复杂度：O（logN）
     * 稳定
     * */
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }
    public static void mergeSortFunc(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        int mid=(start+end)/2;
        //分解
        mergeSortFunc(array,start,mid);
        mergeSortFunc(array,mid+1,end);
        //合并
        merge(array,start,mid,end);
    }
    public static void merge(int[] array,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2 =mid+1;
        int e2=right;

        int[] tempArr = new int[right-left+1];
        int k=0;//tempArr的下标
        //同时满足 证明两个归并段都有数据
        while(s1<=e1 && s2<e2){
            if(array[s1]<=array[s2]){
                tempArr[k++]=array[s1++];
            }else{
                tempArr[k++]=array[s2++];
            }

        }
        while(s1<=e1){
            tempArr[k++]=array[s1++];
        }
        while(s2<=e2){
            tempArr[k++]=array[s2++];
        }
        //排好序的数据拷贝到原来的array中
        for(int i=0;i<tempArr.length;i++){
            array[i+left]=tempArr[i];
        }
    }


    //非递归实现 归并排序
    public static void mergeSortNor(int[] array){
        int gap=1;
        while(gap<array.length){
            for(int i=0; i<array.length;i=i+gap*2){
                int left = i;
                //mid right可能会越界
                int mid=left+gap-1;
                int right=mid+gap;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>=array.length){
                    right=array.length-1;
                }

                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
}
